package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.TreeNode;
import pro.softzhang.algo.flag.knowledge.KBinaryTree;

/**
 * 98. 验证二叉搜索树
 * https://leetcode.cn/problems/validate-binary-search-tree/description/
 */
@KBinaryTree
public class LC98_ValidateBinarySearchTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null));
        boolean f = new Solution().isValidBST(root);
        System.out.println(f);
    }




    /**
     * 中序遍历
     */
    static
    class Solution {
        long preNodeVal = Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) {
            if (root == null) return true;

            if (!isValidBST(root.left)) return false;

            if (root.val <= preNodeVal) return false;

            preNodeVal = root.val;
            return isValidBST(root.right);
        }
    }


    /**
     *  前序遍历
     */
    static
    class Solution1 {
        public boolean isValidBST(TreeNode root) {
            return isValidBST0(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        private boolean isValidBST0(TreeNode root, int left, int right) {
            if (root == null) return true;
            int x = root.val;
            return left < x && x < right && isValidBST0(root.left, left, x) && isValidBST0(root.right, x, right);
        }
    }

    /**
     * 后续遍历
     */
    static
    class Solution2 {
        public boolean isValidBST(TreeNode root) {
            return f(root)[1] != Integer.MAX_VALUE;
        }

        private int[] f(TreeNode node) {
            if (node == null) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE};
            int[] l = f(node.left);
            int[] r = f(node.right);
            int x = node.val;
            if(x <= l[1] || x >= r[0]) {
                return new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE};
            }
            return new int[]{Math.min(l[0], x), Math.max(r[1], x)};
        }
    }
}
